#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    vector<int> findSquare(vector<vector<int>>& matrix) {
        vector<vector<int>>w(matrix.size() + 1);
        vector<vector<int>>h(matrix.size() + 1);
        for (int i = 0; i < matrix.size() + 1; ++i) {
            w[i].resize(matrix.size() + 1);
            h[i].resize(matrix.size() + 1);
        }
        vector<int>res(3);
        for (int i = 1; i <= matrix.size(); ++i) {
            for (int j = 1; j <= matrix.size(); ++j) {
                if (matrix[i - 1][j - 1] == 1) continue;
                w[i][j] = w[i][j - 1] + 1;
                h[i][j] = h[i - 1][j] + 1;
                for (int k = min(w[i][j], h[i][j])-1; k >=0; --k) {
                    int a = min(h[i][j - k], w[i - k][j]);
                    if (a < k + 1) continue;
                    a = min(a, k + 1);
                    if (res[2] < a || (res[2] == a && res[0] > i - a) || (res[2] == a && res[0] == i - a && res[1] > j - a)) {
                        res[0] = i - a;
                        res[1] = j - a;
                        res[2] = a;
                    }
                    break;
                }
            }
        }
        if (res[2] == 0) return {};
        return res;
    }
};

int main() {
    vector<vector<int>> matrix = { {1,0,1} ,{0,0,1},{0,0,1} };
    Solution sol;
    sol.findSquare(matrix);
}